1. Field of the Invention
The present invention relates to an image encoding and decoding apparatus and in particular relates to lossless predictive encoding on inputted image information of multi-value.
2. Discussion of the Related Art
In general, an image has a large amount of data, and therefore, it is normally compressed by encoding when it is to be stored or transmitted. The encoding method of the image data is roughly classified into a lossless encoding method and a lossy encoding method.
In the former case, there is a one-to-one correspondence between the image and the code, and no deterioration of image quality occurs in decoding, but there is a problem that the control of the code amount is difficult. For example, according to Shannon's theorem of information source encoding, it is impossible to make an average code length smaller than the entropy (see, for example, "A guide for document data compressing algorithm", T. Uematsu, CQ publishing company, pp. 32-33). Consequently, in the case where the code amount is limited by some restrictions, it is required to positively reduce the amount of necessary information of the image itself. This is the lossy encoding method.
Here, the entropy is described. The entropy is the sum of the expected values of the information amount outputted per each of the symbols outputted from an information source from which an event occurs randomly and independently of the other events, and defined by the following relation. EQU H=-.SIGMA.P (ai)log.sub.2 P (ai) (1)
P (ai) represents an occurrence rate of i-th symbol ai, and .SIGMA. represents the sum of all symbols. Next, the entropy is calculated by using the specific example shown in FIG. 7. In the figure, there are 6 symbols a1-a6 and the sum of the number of times of occurrence is 24. The result of calculation of the entropy by utilizing the relation (1) is 2.418 bits. According to Shannon's theorem of information source encoding, it is impossible to make the average code length not more than 2.418 bits. In other words, since the sum of the number of times of symbol occurrence is 24, the bit number not less than 2.418.times.24=58.03 is at least required for representation of the symbol string shown in FIG. 7. In the figure, a result of calculation of the average code length by utilizing code words actually assigned is 2.5 bits; accordingly, it is necessary to have 2.5.times.24=60 bits for representation of the symbol string.
Next, the predictive encoding of the lossless encoding method is described. The predictive encoding is a technique for predicting the value of an object pixel based on the states of neighboring pixels which have been processed, and if the prediction results in failure, the prediction error is regarded as a code. The prediction error is a difference between the values of the object pixel and the neighboring pixel, which is obtained by the following relation, for example. EQU d=X-A (2)
Here, d, X and A represent the values of the prediction error, object pixel and neighboring pixel, respectively.
In the predictive encoding, the size and distribution of the prediction error have an influence on the code amount. For example, in an image without noise rendered by a page description language (abbreviated as PDL), the code amount is small. In contrast, in a scanned-in image having noise, the code amount is large.
Now, a method of predictive encoding (Japanese Patent Application No. 8-31074) proposed by the inventors of the present invention is described as an example.
FIG. 8(a) and 8(b) are block diagrams showing constructions of the encoding apparatus and decoding apparatus disclosed in Japanese Patent Application No. 8-31074.
The encoding apparatus shown in FIG. 8(a) is constructed as follows. An image inputting element 10 receives inputted image information from the outside, and forwards it to a first prediction element 20, a second prediction element 21 and a prediction error calculating element 30 as image data 100. Each of the first prediction element 20 and the second prediction element 21 predicts the pixel value of an object pixel based on the image data 100 according to each predetermined manner, and forwards it to a selecting element 40 as predicted value data 110. A prediction error calculating element 30 predicts the pixel value of the object pixel based on the image data 100 according to the predetermined manner and calculates the difference between the predicted value and an actual value of the object pixel, and then forwards the difference to the selecting element 40 as prediction error data 120. The selecting element 40 examines whether the prediction as to the object pixel succeeds or fails based on the image data 100 and the predicted value data 110. As a result, if there is any prediction element which succeeds in prediction, an identification number of the element is converted into prediction state data 130 and forwarded to an encoding element 50. If no prediction element succeeds in prediction, the prediction error data 120 is converted into the prediction state data 130 and then forwarded to the encoding element 50. The encoding element 50 executes encoding of the prediction state data 130 to generate code data 140 by utilizing a predetermined encoding manner, and forwards it to a code outputting element 60. The code outputting element 60 outputs the code data 140 to the outside as output code.
Each part of the decoding apparatus shown in FIG. 8(b) is described next. Elements corresponding to elements of the encoding apparatus have the same reference numbers as those of the encoding apparatus, and explanations are omitted. A code inputting element 70 receives an inputted code from the outside, and forwards it to a decoding element 51 as the code data 140. The decoding element 51 decodes the code data 140 by a decoding manner which is a counterpart of the encoding manner used in the encoding element 50, and forwards it to a selecting element 41 as the prediction state data 130. If the prediction state data 130 indicates an identification number of a prediction element, the selecting element 41 forwards control data 111 to the relevant prediction element so that the prediction element outputs image data 100. If the content of the prediction state data 130 is the prediction error, the selecting element 41 forwards it to a prediction error adding element 31 as the prediction error data 120. The prediction error adding element 31 predicts the pixel value of the object pixel by the manner same as that of the prediction error calculating element 30, restores the pixel value based on the predicted value and the prediction error data 120, and forwards it to an image outputting element 80 as the image data 100. Then the image outputting element 80 outputs the image data 100 to the outside as a decoded image.
Operations according to the encoding manner and decoding manner with the above constructions are now described. FIG. 9(a) and 9(b) are flow charts showing the operations.
Encoding operations are explained first based on FIG. 9(a). In step 10, an image is inputted to the image inputting element 10 to obtain the image data 100. In step 20, the pixel value prediction of the object pixel is performed in the first prediction element 20 and the second prediction element 21 based on the image data 100, and at the same time, the prediction error of the predicted value is calculated by a predetermined manner in the prediction error calculating element 30.
In step 30, it is determined in the selecting element 40 whether the predicted value of the first prediction element is identical with the pixel value of the object pixel. If these two values are identical, the identification number of the prediction element which succeeded in prediction is converted into the prediction state data 130 and forwarded to the encoding element 50. If these values are not identical, it is determined whether the predicted value of the second prediction element is identical with the pixel value of the object pixel, and if these values are identical, the identification number of the prediction element which succeeded in prediction is converted into the prediction state data 130 and forwarded to the encoding element 50. If two values are not identical, the prediction error data 120 is converted into the prediction state data 130 and forwarded to the encoding element 50.
In step 40, the prediction state data 130 is encoded in the encoding element 50 by a predetermined encoding manner to obtain the code data 140. In step 50, the code outputting element 60 outputs the code data 140 to the outside. In step 60, it is determined whether all pieces of inputted image data have been processed, and if processing of all pieces of data has been completed, the encoding process is finished. If there is any data left unprocessed, the process returns to the step 10.
Next, decoding operations are described based on FIG. 9(b). In step 110, the code is inputted to the code inputting element 70 to obtain the code data 140. In step 120, in the decoding element 51, the prediction state data 130 is obtained from the code data 140 by utilizing a decoding manner which is a counterpart of the encoding manner used in the encoding element 50.
In step 130, it is determined in the selecting element 41 whether the prediction state data 130 is identical with the identification number of the first prediction element. If these values are identical with each other, the control data 111 is forwarded to the first prediction element 20. If these values are not identical, it is determined whether the prediction state data 130 is identical with the identification number of the second prediction element. If these values are identical with each other, the control data 111 is forwarded to the second prediction element 21. In the case where these values are not identical, the prediction state data 130 is converted into the prediction error data 120 in the selecting element 41, and forwarded to the prediction error adding element 31.
In step 21, if there is any prediction element which receives the control data 111, the relevant prediction element outputs the value of the object pixel predicted by itself as the image data 100. In the case where no prediction element receives the control data 111, the pixel value is restored in the prediction error adding element 31 based on the prediction error data 120 and the predicted value obtained by the manner same as that of the prediction error calculating element 30, and outputted as the image data 100. In step 140, the image outputting element 80 outputs the image data 100 to the outside. In step 150, it is determined whether all inputted code data are processed, and if all data have been processed, the decoding process is finished. In the case there are the data left unprocessed, the process returns to step 110.
In the encoding apparatus and decoding apparatus with the above constructions, the size and the distribution of the prediction error influence the code amount as described so far. FIG. 10 shows examples of distribution of prediction error in two images, one of which is rendered by PostScript (trademark of Adobe Systems Incorporated), a kind of the PDLs, and the other one is a scanned-in image. The image rendered by PostScript has no noise; accordingly, the object pixel and the neighboring pixel is closely correlated, and as a result, the distribution of prediction errors is locally biased around zero as shown in FIG. 10. In this case, the entropy calculated by the relation (1) by utilizing the prediction error represented by the relation (2) becomes small, and thereby the code amount can be reduced. In contrast, the scanned-in image has some noise and the object pixel and the neighboring pixel has correlation of low level; therefore, the distribution of prediction errors is less biased around zero as shown in FIG. 10. The result of entropy calculation using the prediction error represented by the relation (2) is large, whereby the code amount also becomes large. In the example of Japanese Patent Application No. 8-31074, the code amount of the image having close correlation between the object pixel and the neighboring pixel, such as an image rendered by PDL, is effectively reduced.
However, as the inputted image information, there is a tag as well as the pixel values such as the image rendered by the PDL or the scanned-in image. The tag is the additional information about the output image, which indicates, for example, switching of the image rendered by the PDL and that inputted by scanning, switching of encoding method, switching of resolution, or the like. The bit number of the pixel value is 8 bits, for example, whereas the bit number of the tag is 1 bit or more. In many cases, the bit number of the tag is smaller than that of the pixel value. For instance, the tag indicating switching of an image rendered by the PDL and a scanned-in image requires 1 bit, and the tag indicating switching of the encoding methods or resolutions requires 1-3 bits.
In the case where a tag having a bit number smaller than that of a pixel value is encoded by utilizing the encoding method disclosed in Japanese Patent Application No. 8-31074, the compressing efficiency is lower than that of the pixel value. For example, it is assumed that the pixel value has 8 bits, the tag has 1 bit and the predicted value data 110 of FIG. 8 has 2 bits. Supposing that the prediction is succeeded, 8 bits of the pixel value is reduced to 2 bits, and the amount of data is reduced to 1/4. In the case of tag, 1 bit increases to 2 bits, and thereby the amount of data becomes larger.
Therefore, if the bit number of the tag is smaller than that of the pixel value, it may be possible to carry out packing so that the bit number of the tag becomes equal to that of the pixel value, and then the tag is encoded. Thus the data amount in the case the prediction is succeeded is the same in both of the cases of the pixel value and the tag.
Next is the case where the prediction fails. In the example of Japanese Patent Application No. 8-31074, the prediction error data 120 is generated by the difference between the predicted value and the actual value of the object pixel if the prediction fails, as described above. The reason for taking the difference is that each of the bits constituting the pixel has no significance, but the value of 8 bits as a whole has significance as a pixel value, and moreover, the correlation exists between the pixels. To the contrary, the tag packed to unit data having 8 bits (hereinafter, this is simply referred to as the tag) has significance in each of the bits constituting the tag in this example, and there is little significance as a value of 8 bits as a whole. The correlation between each of the bits constituting the tag is closer than that between the tags. Accordingly, in the case where the prediction fails, the information indicating how many different bits a couple of tags have is more significant than the information obtained by the difference between the tags.
As an operation satisfying such conditions, exclusive OR can be considered, for example. The exclusive OR is a bit operation which outputs 0 if two factors have the same value, or outputs 1 if two factors have different values. Consequently, in some cases, generation of the prediction error data 120 using the exclusive OR, rather than using the difference leads to closer correlation between the tags and the reduction of the code amount dependent on the type of the tag.
As described above, in the case where the inputted image information is other than the pixel value and has a bit number smaller than the pixel value, such as a tag, and besides the prediction fails, generation of the prediction error data 120 based on the difference as disclosed in Japanese Patent Application No. 8-31074 reduces correlation between the pieces of inputted image information, and therefore the code amount cannot be reduced.